 /********************************************************************************************\
 * libeds - extensible data structures library                                                *
 * Copyright (C) 2006, Dan Kruchinin, <just.asgard@gmail.com>                                 *
 *                                                                                            *
 * -> trees/rnd_tree.h                                                                        *
 *                                                                                            *
 * This library is free software; you can redistribute it and/or modify it under the terms of *
 * the GNU Lesser General Public License as published by the Free Software Foundation;        *
 * either version 2.1 of the License, or (at your option) any later version.                  *
 *                                                                                            *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;  *
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  *
 * See the GNU Lesser General Public License for more details.                                *
 *                                                                                            *
 * You should have received a copy of the GNU Lesser General Public License along with this   *
 * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,  *
 * Boston, MA 02111-1307 USA                                                                  *
 \********************************************************************************************/

#ifndef DS_RND_TREE_H
#define DS_RND_TREE_H

#include <stdlib.h>
#include "ds.h"
#include "trees/bin_tree.h"

/*
 *
 * random condition will be used for balancing(near).
 * it implemented as macro for easy replacing such conditional
 *
 */
#define RANDOM_CONDITION(n)									\
  ((random() < (RAND_MAX / ((n)->_nofnodes + 1))) ? 1 : 0)

/* strcuture is quite simple, there no any extra functions or information */
typedef struct rnd_tree {
  struct _bit* tree;
  BIT_DEFAULT_FUNCS(struct rnd_tree);
} rnd_tree;

#define bit2rnd_tree(tree)						\
  BIT_CONVERTION(tree, rnd_tree)

rnd_tree* rnd_create(void);
rnd_tree* rnd_join(rnd_tree*, rnd_tree*);
rnd_tree* rnd_join_by_cond(rnd_tree*, rnd_tree*, void*, void*);
rnd_tree* rnd_split(rnd_tree*, bit_node*);
void rnd_destroy(rnd_tree*);

#endif /* DS_RND_TREE_H */
